import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/7 10:23
 * @description 单调栈1 存储的是值
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,2,3,4,3};
        solution.nextGreaterElements(nums);
    }
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        // 键是元素，值是下一个更大元素值
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 2 * n - 1; i >= 0; i--) {
            // 复制一份，但是可省略建新数组
            int num = nums[i % n];
            // 正常单调栈思路
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            // 注意不能放num，重复数据会覆盖
            map.put(i, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = map.get(i);
        }
        return ans;
    }
}
